西瓜书4 决策树

4.1 决策树基本概念

决策过程的每一次判定都是对某一属性的“测试”，决策最终结论则对应最终的判定结果。一般一颗决策树包含：一个根节点、若干个内部节点和若干个叶子节点，易知：

每个非叶节点表示一个特征属性测试。
每个分支代表这个特征属性在某个值域上的输出。
每个叶子节点存放一个类别。
每个节点包含的样本集合通过属性测试被划分到子节点中，根节点包含样本全集。

4.2 决策树的构造

决策树的构造是一个递归的过程，有三种情形会导致递归返回：(1) 当前结点包含的样本全属于同一类别，这时直接将该节点标记为叶节点，并设为相应的类别；
(2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分，这时将该节点标记为叶节点，并将其类别设为该节点所含样本最多的类别；
(3) 当前结点包含的样本集合为空，不能划分，这时也将该节点标记为叶节点，并将其类别设为父节点中所含样本最多的类别。
算法的基本流程如下图所示：
Pasted image 20250320162220.png

直观理解💡

先看数据 $D$ 是不是“纯净”（第2-4行）：如果所有样本的标签都一样（比如全是“狗”），就不用再分了，直接把这个标签记在节点上，返回。

再看特征集 $A$ 或者数据 $D$ 是不是用完了（第5-7行）：如果没特征可用，或者数据里特征值都一样，那就挑一个最多的标签当答案，返回。

如果还能分（第8-16行），就从 $A$ 里挑一个最厉害的特征 $a^{*}$ （比如“四条腿？”），然后根据这个特征的每个可能值（是/否），把数据分成几份（比如“四条腿的”和“不是四条腿的”），对每份数据再递归调用自己，继续种树。

它的核心是“挑特征”和“递归”，就像你种树时先选主干，再长树杈。最难的是啥？挑“最优特征” $a_{*}$ （第8行）咋挑？得用数学方法（比如信息增益），不然树会歪，预测就不准了。

可以看出：决策树学习的关键在于如何选择划分属性，不同的划分属性得出不同的分支结构，从而影响整颗决策树的性能。属性划分的目标是让各个划分出来的子节点尽可能地“纯”，即属于同一类别。因此下面便是介绍量化纯度的具体方法，决策树最常用的算法有三种：ID3，C4.5和CART。

4.2.1 ID3算法信息增益

信息熵(information entropy)用来衡量一个数据集“混乱程度”的指标。
- $E n t (D) = - \sum_{k = 1}^{| Y |} p_{k} \log_{2} p_{k}$
  - $D$ ：当前样本集合，也就是你要分析的数据集。
  - $Y$ ：样本的类别集合，比如“是”或“否”、“喜欢”或“不喜欢”， $| Y |$ 就是类别的总数。
  - 假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_{k} (p = 1, 2, . . ., | Y |)$
  - 约定：若 $p = 0$ ，则 $p \log_{2} p = 0$
- $0 \leq E n t (D) \leq \log_{2} | Y |$
  - 熵越小，纯度越高：如果所有样本都属于同一类（比如全是“喜欢”）， $p_{1} = 1$ ，其他 $p_{k} = 0$ ，代入公式算出来 $E n t (D) = 0$ ，这时候数据集完全不混乱，纯度最高。
  - 熵越大，纯度越低：如果各类样本数量差不多（比如一半“喜欢”，一半“不喜欢”），熵会达到最大值 $\log_{2} | Y |$ ，混乱程度最高。
信息增益 (Information Gain)：是用来衡量某个属性（特征）对数据集分类的效果。
- $G a i n (D, a) = E n t (D) - \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} E n t (D^{v})$
  - $a$ ：某个属性，比如“天气”或“心情”。
  - $V$ ：属性 $a$ 有 $V$ 个可能的取值，比如“天气”可以是 {晴,雨}，那 $V$ = 2。
  - $D_{v}$ ：数据集 $D$ 中属性 $a$ 取值为 $a_{v}$ 的子集。比如“天气=晴”的样本子集。
  - | $D_{v}$ | 和 | $D$ |：分别是子集和总数据集的样本数， $\frac{| D_{v} |}{| D |}$ 是子集占总体的比例。
  - $E n t (D_{v})$ ：子集 $D_{v}$ 的信息熵。
- 计算过程：原始数据集的熵 $E n t (D)$ ，减去按属性 $a$ 划分后所有子集熵的加权平均。
  - 意义：信息增益越大，说明用这个属性划分后，数据集的混乱程度减少得越多，这个属性就越重要。
ID3算法：核心思想是每次通过看信息增益，选择一个“最好”的属性来划分数据集。
- $a^{*} = \underset{a \in A}{argmax} Gain (D, a)$

4.2.2 C4.5算法增益率

信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5决策树算法使用“增益率”(gain ratio)来选择最优划分属性
- 原因：当属性 $a$ 的取值数目 $V$ 很多时（例如一个属性是“ID 编号”，每个样本的取值都不同），划分后的每个子集 $D_{v}$ 可能只包含少量样本甚至单个样本。这种情况下，子集的熵 $E n t (D_{v})$ 很小（甚至为 0），导致信息增益 $G a i n (D, a)$ 很大。
- 缺点：这种划分虽然信息增益高，但会导致决策树过拟合（树太深，叶子节点样本太少），缺乏泛化能力。
增益率： $G a i n_r a d i o (D, a) = \frac{G a i n (D, a)}{I V (a)}$
- 其中：定义属性 $a$ 的固有值 $I V (a) = - \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} \log_{2} \frac{| D^{v} |}{| D |}$
- 固有值 $I V (a)$ 的意义
  - $I V (a)$ 是属性 $a$ 取值分布的熵，反映了属性本身的划分特性。
  - 属性 $a$ 的取值数目 $V$ 越多，且各子集样本分布较均匀时， $I V (a)$ 的值通常越大。例如：
    - 如果 $a$ 有 100 个取值，且每个取值的样本数相等，则 $I V (a)$ 较大。
    - 如果 $a$ 只有 2 个取值，则 $I V (a)$ 较小。
- 增益率的作用
  - 增益率通过将信息增益除以 $I V (a)$ ，对取值数目较多的属性施加了一个“惩罚”。
  - 效果：
    - 当 $V$ 很大时， $I V (a)$ 较大，增益率 $G a i n_r a t i o (D, a)$ 被压低。
    - 当 $V$ 较小时， $I V (a)$ 较小，增益率相对较高。
尽管增益率解决了信息增益的缺点，但它本身也存在偏好：偏好取值数目较少的属性。
- 原因：如果属性 $a$ 的取值数目 $V$ 很小（极端情况下只有 1 个取值）， $I V (a)$ 会非常小，分母变小会导致增益率变得很大.
- 问题：取值数目过少的属性划分能力可能很弱（甚至无法划分数据），选择这样的属性对构建决策树没有实际意义。
为了平衡信息增益和增益率的优缺点，C4.5算法 并不直接选择增益率最高的属性，而是采用了一个 启发式方法：
1. 计算所有候选属性的信息增益。
2. 筛选出信息增益高于平均水平的属性（即信息增益大于所有候选属性信息增益的平均值）。
3. 从这些属性中选择增益率最高的属性作为最优划分属性。

4.2.3 CART算法

分类与回归树（Classification and Regression Trees）

G i n i (D) = 1 - \sum_{k = 1}^{| Y |} p_{k}^{2}

基尼指数（Gini Index） $G i n i (D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此， $G i n i (D)$ 越小，则数据集 $D$ 的纯度越高

属性 $a$ 的基尼指数定义： $G i n i_i n d e x (D, a) = \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} G i n i (D^{v})$
$a^{*} = \underset{a \in A}{argmin} Gain_index (D, a)$

在构造 CART 决策树时，并不会严格按照此式来选择最优划分属性，主要是因为 CART 决策树是一棵二叉树，如果用上式去选出最优划分属性，无法进一步选出最优划分属性的最优划分点。
(基尼指数这个公式适合多叉树，比如属性“天气”有三个取值（晴、雨、阴），直接分成三份。但 CART 是二叉树，它要求每次只能分成两份。如果只用这个公式挑了个属性（比如“天气”），你还是不知道具体怎么分两份——是“晴 vs 非晴”？还是“雨 vs 非雨”？光选属性不够，还得定一个具体的“点”来切开数据。所以，CART 不用这个公式直接选属性，而是换了个更适合二叉树的办法。)

常用的 CART 决策树的构造算法如下：

考虑每个属性 $a$ 的每个可能取值 $v$ ，将数据集 $D$ 分为 $a = v$ 和 $a \neq v$ 两部分来计算基尼指数，即： $G i n i_i n d e x (D, a) = \frac{| D^{a = v} |}{| D |} G i n i (D^{a = v}) + \frac{| D^{a \neq v} |}{| D |} G i n i (D^{a \neq v})$
选择基尼指数最小的属性及其对应取值作为最优划分属性和最优划分点
重复以上两步，直至满足停止条件

4.3 剪枝处理

从决策树的构造流程中我们可以直观地看出：不管怎么样的训练集，决策树总是能很好地将各个类别分离开来，这时就会遇到之前提到过的问题：过拟合（overfitting），即太依赖于训练样本。剪枝（pruning）则是决策树算法对付过拟合的主要手段，剪枝的策略有两种如下：

预剪枝（prepruning）：在构造的过程中先评估，再考虑是否分支。
后剪枝（post-pruning）：在构造好一颗完整的决策树后，自底向上，评估分支的必要性。

评估指的是性能度量，即决策树的泛化性能。之前提到：可以使用测试集作为学习器泛化性能的近似，因此可以将数据集划分为训练集和测试集。预剪枝表示在构造数的过程中，对一个节点考虑是否分支时，首先计算决策树不分支时在测试集上的性能，再计算分支之后的性能，若分支对性能没有提升，则选择不分支（即剪枝）。后剪枝则表示在构造好一颗完整的决策树后，从最下面的节点开始，考虑该节点分支对模型的性能是否有提升，若无则剪枝，即将该节点标记为叶子节点，类别标记为其包含样本最多的类别。

未剪枝決策树：

预剪枝决策树：

后剪枝决策树：

预剪枝处理使得决策树的很多分支被剪掉，因此大大降低了训练时间开销，同时降低了过拟合的风险，但另一方面由于剪枝同时剪掉了当前节点后续子节点的分支，因此预剪枝“贪心”的本质阻止了分支的展开，在一定程度上带来了欠拟合的风险。而后剪枝则通常保留了更多的分支，因此采用后剪枝策略的决策树性能往往优于预剪枝，但其自底向上遍历了所有节点，并计算性能，训练时间开销相比预剪枝大大提升。

4.4 连续值与缺失值处理

连续值处理

连续属性离散化的基本思想
在决策树中，连续属性（比如温度、身高等）具有无限多个可能取值，无法像离散属性那样直接用于划分数据集。
二分法的核心：给定样本集 $D$ 和连续属性 $a$ ，二分法试图找到一个划分点 $t$ ，将 $D$ 分为两部分：
$D_{t}^{-}$ ：属性 $a$ 的取值满足 $a \leq t$ 的样本子集。
$D_{t}^{+}$ ：属性 $a$ 的取值满足 $a > t$ 的样本子集。
目标：找到一个最优的 $t$ ，使得划分后的子集在某种准则下（如纯度更高）表现最佳。
划分点的选择
为了找到最佳划分点 $t$ ，CART 需要系统地考察所有可能的候选划分点。具体步骤如下：
排序：
假设连续属性 $a$ 在样本集 $D$ 上有 $n$ 个不同的取值，将这些取值从小到大排序，记为 ${a_{1}, a_{2}, \dots, a_{n}}$ 。
生成候选划分点：
对于任意相邻的取值 $a_{i}$ 和 $a_{i + 1}$ ，在区间 $[a_{i}, a_{i + 1})$ 中选择一个点作为候选划分点。
通常选择中位点 $\frac{a_{i} + a_{i + 1}}{2}$ 作为候选划分点，因为在 $[a_{i}, a_{i + 1})$ 内的任意 $t$ 产生的划分结果相同。
因此，候选划分点集合为：

T_{a} = {\frac{a_{i} + a_{i + 1}}{2} | 1 \leq i \leq n - 1}

总共有 $n - 1$ 个候选划分点。
逐一评估：
对 $T_{a}$ 中的每个 $t$ ，计算划分后的某种指标（如信息增益或基尼指数），选择最优的 $t$ 。

信息增益的计算
信息增益的定义：对于样本集 $D$ 和属性 $a$ 在划分点 $t$ 上的信息增益 $G a i n (D, a, t)$ ，计算公式为：

G a i n (D, a, t) = E n t (D) - \sum_{λ \in {-, +}} \frac{| D_{t}^{λ} |}{| D |} E n t (D_{t}^{λ})

其中：
$E n t (D)$ ：划分前数据集 $D$ 的熵，表示数据的混乱程度。
$D_{t}^{-}$ ： $a \leq t$ 的子集。
$D_{t}^{+}$ ： $a > t$ 的子集。
$| D_{t}^{λ} |$ ：子集 $D_{t}^{-}$ 或 $D_{t}^{+}$ 的样本数。
$E n t (D_{t}^{λ})$ ：子集的熵。
$| D |$ ：数据集 $D$ 的总样本数。

最佳划分点：对 $T_{a}$ 中的每个 $t$ 计算 $G a i n (D, a, t)$ ，选择使信息增益最大的 $t$ ：

G a i n (D, a) = max_{t \in T_{a}} G a i n (D, a, t)

缺失值处理

缺失值填充方法
假设：数据集中的样本是基于独立同分布（i.i.d.）采样得到的。
常用的缺失值填充方法如下：
连续属性：使用该属性的均值进行填充。
离散属性：使用该属性值中个数最多的样本值（即众数）进行填充。
这种方法简单高效，但在属性值缺失的情况下，决策树的构建还需要更细致的处理方式，如下所述。
定义与符号
给定训练集 $D$ 和属性 $a$ ，属性 $a$ 有 $V$ 个可取值 $a_{1}, a_{2}, \dots, a_{V}$ 。以下是相关定义：
$\tilde{D}$ ： $D$ 中在属性 $a$ 上没有缺失值的样本子集
${\tilde{D}}^{v}$ ： $\tilde{D}$ 中在属性 $a$ 上取值为 $a^{v}$ 的样本子集
${\tilde{D}}_{k}$ ： $\tilde{D}$ 中属于第 $k$ ( $k = 1, 2, . . ., | Y |$ ) 类的样本子集
$w_{x}$ ：样本 $x$ 的权重
无缺失值样本所占比例：$$\rho=\frac{\sum_{x\in \widetilde{D} }w_x}{\sum_{x\in {D} }w_x}$$
无缺失值样本中第 $k$ 类所占的比例：$$\widetilde{p}k=\frac{\sum{x\in \widetilde{D}k }w_x}{\sum{x\in \widetilde{D} }w_x}$$
无缺失值样本中在属性 $a$ 上取值 $a^{v}$ 的样本所占比例：$$\widetilde{r}v=\frac{\sum{x\in \widetilde{D}^v }w_x}{\sum_{x\in \widetilde{D} }w_x}$$

G a i n (D, a) = ρ \times G a i n (\tilde{D}, a) = ρ \times [E n t (\tilde{D}) - \sum_{v = 1}^{V} {\tilde{r}}_{v} E n t ({\tilde{D}}^{v})]

其中： $E n t (\tilde{D}) = - \sum_{k = 1}^{| Y |} {\tilde{p}}_{k} \log_{2} {\tilde{p}}_{k}$

属性选择：如何在属性值缺失的情况下选择划分属性？
在属性值缺失的情况下，属性选择仅基于无缺失值样本子集 $D$ 来判断属性 $a$ 的优劣。具体方法是通过计算信息增益 $G a i n (D, a)$ 来评估属性 $a$ 的划分能力。
信息增益的计算公式为：

G a i n (D, a) = ρ \times G a i n (\tilde{D}, a)

其中：

G a i n (\tilde{D}, a) = E n t (\tilde{D}) - \sum_{v = 1}^{V} {\tilde{r}}_{v} E n t ({\tilde{D}}^{v})

熵 $E n t (\tilde{D})$ 的定义为：

E n t (\tilde{D}) = - \sum_{k = 1}^{| Y |} {\tilde{p}}_{k} \log_{2} {\tilde{p}}_{k}

解释：
$E n t (\tilde{D})$ 表示无缺失值样本子集 $\tilde{D}$ 的熵，衡量其类别的不确定性。
$\sum_{v = 1}^{V} {\tilde{r}}_{v} E n t ({\tilde{D}}^{v})$ 表示按属性 $a$ 划分后各子集的加权熵。
$ρ$ 是无缺失值样本的比例，用于对信息增益进行加权调整，确保考虑缺失值的影响。

因此，属性选择的步骤是：
计算 $D$ 的信息增益 $G a i n (\tilde{D}, a)$ 。
用 $ρ$ 加权得到 $G a i n (D, a)$ 。
比较各属性的 $G a i n (D, a)$ ，选择信息增益最大的属性作为划分属性。

样本划分：给定划分属性后如何处理缺失值样本？
在确定划分属性 $a$ 后，需要将样本划入对应的子结点。根据样本在属性 $a$ 上的取值是否已知，划分方法分为两种情况：

（1）样本在属性 $a$ 上的取值已知
划分规则：若样本 $x$ 在属性 $a$ 上的取值为 $a_{v}$ （已知），则将 $x$ 划入与 $a_{v}$ 对应的子结点。
权值处理：样本 $x$ 在子结点中的权值保持为 $w_{x}$ 。

（2）样本在属性 $a$ 上的取值未知
划分规则：若样本 $x$ 在属性 $a$ 上的取值缺失，则将 $x$ 同时划入所有子结点。
权值处理：样本 $x$ 在与属性值 $a_{v}$ 对应的子结点中的权值调整为：
$r^{v} \cdot w_{x}$

其中 $r^{v}$ 是无缺失值样本中属性 $a$ 取值 $a_{v}$ 的比例。

直观理解：这种方法让同一个缺失值样本以不同的概率（由 $r^{v}$ 决定）被分配到不同的子结点，反映了属性值的分布情况。

4.5 多变量决策树

如果我们将每个属性视为坐标系中的一个坐标轴，那么d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类意味着在这个坐标空间当中寻找不同类别的分类边界，决策树所形成的分类边界有一个非常重要的特点，那便是：轴平行（axis-parallel），即其分类边界由若干个与坐标轴平行的分段组成：
Pasted image 20250320185827.png